<!DOCTYPE html>
<html lang="zh-cn">
  <head>
    <meta charset="utf-8" />
    <meta
      name="viewport"
      content="width=device-width, initial-scale=1.0, minimum-scale=1.0, maximum-scale=1.0, user-scalable=no"
    />
    <meta http-equiv="X-UA-Compatible" content="IE=edge,chrome=1" />
    <title>1329. 将矩阵按对角线排序</title>
  </head>
  <body>
    <!-- start -->
    <div>
      地址：https://leetcode.cn/problems/sort-the-matrix-diagonally/description/?envType=daily-question&envId=2024-04-29
    </div>
    <!-- end -->
  </body>
  <!-- js start -->
  <script type="text/javascript">
    /*******************************************************************************
     * 矩阵对角线 是一条从矩阵最上面行或者最左侧列中的某个元素开始的对角线，沿右下方向一直到矩阵末尾的元素。例如，矩阵 mat 有 6 行 3 列，从 mat[2][0] 开始的 矩阵对角线 将会经过 mat[2][0]、mat[3][1] 和 mat[4][2] 。
     * 给你一个 m * n 的整数矩阵 mat ，请你将同一条 矩阵对角线 上的元素按升序排序后，返回排好序的矩阵。
     *
     *
     * 示例 1：
     * https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/01/25/1482_example_1_2.png
     * 输入：mat = [[3,3,1,1],[2,2,1,2],[1,1,1,2]]
     * 输出：[[1,1,1,1],[1,2,2,2],[1,2,3,3]]
     * 示例 2：
     *
     * 输入：mat = [[11,25,66,1,69,7],[23,55,17,45,15,52],[75,31,36,44,58,8],[22,27,33,25,68,4],[84,28,14,11,5,50]]
     * 输出：[[5,17,4,1,52,7],[11,11,25,45,8,69],[14,23,25,44,58,15],[22,27,31,36,50,66],[84,28,75,33,55,68]]
     *
     *
     * 提示：
     * m == mat.length
     * n == mat[i].length
     * 1 <= m, n <= 100
     * 1 <= mat[i][j] <= 100
     ******************************************************************************/
    /**
     * @param {number[][]} mat
     * @return {number[][]}
     */
    var diagonalSort = function (mat) {
      if (mat.length <= 1) return mat;
      return init(mat);
    };

    /** 新矩阵对象 */
    class newDiagonalItem {
      constructor(x, y, val) {
        this.x = x;
        this.y = y;
        this.val = val;
      }
    }

    function init(mat) {
      // 将二维数组转为一维数组
      let newMat = [];

      // 对角线开始数组
      const diagonalStartList = [];

      // 将二维数组转为一维数组
      mat.map((rowItem, rowIndex) => {
        rowItem.map((colItem, colIndex) => {
          let diagonalItem = new newDiagonalItem(rowIndex, colIndex, colItem);

          if (rowIndex === 0 || colIndex === 0) {
            diagonalStartList.push(diagonalItem);
          }
          newMat.push(diagonalItem);
        });
      });

      const diagonalRelList = createDiagonalRelByStart(diagonalStartList, mat);

      //   debugger;
      let res = reductionList(diagonalRelList, mat);

      return res;
    }

    /** 创建对角线关系 */
    function createDiagonalRelByStart(diagonalStartList, mat) {
      // 对角线关系
      const diagonalRelList = [];

      diagonalStartList.map((dSItem) => {
        let dRItem = [dSItem];

        const { x, y, val } = dSItem;
        // debugger;

        dRItem = findNextItem(dRItem, mat, x, y, val);

        diagonalRelList.push(sortDRItem(dRItem));
      });

      return diagonalRelList;

      /** 构建单条对角线 */
      function findNextItem(dRItem, mat, x, y, val) {
        const nextX = x + 1;
        const nextY = y + 1;

        if (mat[nextX] === undefined || mat[nextX][nextY] === undefined) return dRItem;

        const nextVal = mat[nextX][nextY];

        const nextItem = new newDiagonalItem(nextX, nextY, nextVal);
        dRItem.push(nextItem);
        return findNextItem(dRItem, mat, nextX, nextY, nextVal);
      }

      /** 单条对角线内重新排序 */
      function sortDRItem(dRItem) {
        const valList = [];

        dRItem.map((item) => {
          let { x, y, val } = item;
          valList.push(val);
        });

        // 升序
        valList.sort((a, b) => a - b);

        dRItem.map((item, index) => {
          let { x, y } = item;
          item.val = valList[index];
        });

        return dRItem;
      }
    }

    function reductionList(diagonalRelList, mat) {
      let rowLength = mat.length;
      let colLength = mat[0].length;

      const newMat = [];

      diagonalRelList.map((rItem) => {
        rItem.map(({ x, y, val }) => {
          if (newMat[x] === undefined) newMat[x] = [];
          newMat[x][y] = val;
        });
      });

      return newMat;
    }

    /*******************************************************************************
     * 测试
     ******************************************************************************/
    console.log(
      diagonalSort([
        [3, 3, 1, 1],
        [2, 2, 1, 2],
        [1, 1, 1, 2],
      ])
    );
  </script>
</html>
